package 快排;

import java.util.Random;



//给你一个整数数组 nums，请你将该数组升序排列。
//
//你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
public class Solution {

    public int[] sortArray(int[] nums) {
        qsort(nums,0,nums.length-1);
        return nums;
    }
    private void qsort(int[] nums, int l, int r) {
        if(l>=r){
            return;
        }
        int key=nums[new Random().nextInt(r-l+1)+l];
        int i=l;
        int left=l-1;
        int right=r+1;
        while(i<right){
            if(nums[i]<key){
                swap(nums,++left,i++);
            }else if(nums[i]==key){
                i++;
            }else
                swap(nums,--right,i);
        }
    }
    private void swap(int[] nums, int i, int i1) {
        int tmp=nums[i];
        nums[i]=nums[i1];
        nums[i1]=tmp;
    }
}
